//https://leetcode.cn/problems/check-if-there-is-a-valid-path-in-a-grid/

class UnionSet {
private:
    int* parent; // 并查集的父节点数组
    int* size;   // 并查集的集合大小数组，用于按大小合并

public:
    // 构造函数：初始化并查集
    UnionSet(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i; // 每个节点的初始父节点是自己
            size[i] = 1;   // 每个集合的初始大小为1
        }
    }

    // 查找函数（路径压缩优化）
    // 找到元素 x 所属集合的根节点
    int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并函数：合并两个集合，返回是否已经连通
    bool Merge(int x, int y) {
        x = Find(x); // 找到 x 的根节点
        y = Find(y); // 找到 y 的根节点
        if (x != y) {
            // 按大小合并，小集合挂到大集合下面
            if (size[x] < size[y]) {
                swap(x, y);
            }
            parent[y] = x; // y 的根指向 x 的根
            size[x] += size[y]; // 更新 x 集合的大小
            return false; // 合并成功，之前不连通
        }
        return true; // x 和 y 已经连通
    }
};

class Solution {
public:
    // 判断网格是否存在从左上角到右下角的有效路径
    bool hasValidPath(vector<vector<int>>& grid) {
        // 定义横向和纵向可以连通的条件
        // 横向可以连通的格子类型
        vector<int> hv = {1, 1, 1, 3, 1, 5, 4, 1, 4, 3, 4, 5, 6, 1, 6, 2, 6, 5};
        // 纵向可以连通的格子类型
        vector<int> vv = {2, 2, 2, 5, 2, 6, 3, 2, 3, 5, 3, 6, 4, 2, 4, 5, 4, 6};

        int rows = grid.size();    // 网格的行数
        int cols = grid[0].size(); // 网格的列数

        // 初始化并查集，总共 rows * cols 个节点
        UnionSet us(rows * cols);

        // 遍历网格，合并相邻的满足连通条件的单元格
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                // 检查当前格子和右边格子是否可以连通
                if (j != cols - 1) { // 不是最右列
                    for (int k = 0; k < hv.size(); k += 2) {
                        if (hv[k] == grid[i][j] && hv[k + 1] == grid[i][j + 1]) {
                            // 合并当前格子与右边格子
                            us.Merge(i * cols + j, i * cols + j + 1);
                        }
                    }
                }
                // 检查当前格子和下方格子是否可以连通
                if (i != rows - 1) { // 不是最下行
                    for (int k = 0; k < vv.size(); k += 2) {
                        if (vv[k] == grid[i][j] && vv[k + 1] == grid[i + 1][j]) {
                            // 合并当前格子与下方格子
                            us.Merge(i * cols + j, (i + 1) * cols + j);
                        }
                    }
                }
            }
        }

        // 检查左上角（0,0）和右下角是否连通
        return us.Merge(0, rows * cols - 1);
    }
};
